不会真的有人在考了 n 次后还不会一个算法吧 不会吧不会吧
老早就学了这玩意,但是几次考试板子也写不对。于是近期重新梳理了一下算法。
算法流程
假设现在有一个函数 f(i) ,我们要求下式的值:
i=1∑nf(i)
构造函数 F(i),满足如下要求:
- 方便求前缀和
- 在质数处的取值与 f(i) 相同
- 完全积性函数
设 pi 表示第 i 个质数。
设 G(n,i) 表示「前 n 个数中,质数 或者 最小质因子大于 pi 的数的 F(i) 之和」。注意 G 的求和不包含 1 。
换一个更加直观的说法:在埃式筛中,第 i 轮后仍然未被筛去的数的 F(i) 之和。
可以写出转移方程:
G(n,i)=⎩⎪⎨⎪⎧G(n,i−1) pi2>nG(n,i−1)−F(pi)(G(⌊pin⌋,i−1)−j=1∑i−1F(pj)) pi2≤n
首先,第 i 轮筛后仍未被筛去的数的 F(i) 之和一定是第 i−1 轮后的一部分,我们先继承过来再考虑减去多算的。可以发现,第 i 轮筛一定至少从 pi2 开始,所以若 pi2>n 那么什么都不会发生;否则,我们从所有应该被筛去的数的函数值中提出 F(pi) (注意:此时用到了「完全积性函数」的性质),然后剩下的数的最小质因子都必须大于 pi−1 ,所以它们的函数值和在 G(⌊pin⌋,i−1) 中。但是 G(⌊pin⌋,i−1) 中还多算了比 pi 小的质数的函数值之和,所以这部分我们也得减去。
考虑完转移,我们来考虑如何设置初值。显然,G(n,0) 就相当于什么都没有筛,也就是 F(i) 的前缀和。所以我们需要这个函数「方便求前缀和」。
设 limit 表示 n 以内的所有质数, 那么由于保证了「F(i) 在质数处的取值与 f(i) 相同」, G(n,limit) 就是 n 以内的所有质数的 f(i) 的和。上述一大堆的工作,目的皆在于此——对于任意 n ,求出 n 以内的质数的 f(i) 之和。
下面我们来考虑求所有合数的值。设 S(n,i) 表示「前 n 个数中,最小质因子大于等于 pi 的合数的 f(i) 之和」。同样的,S 的求和中是不包含 1 的。
可以写出转移方程:
S(n,i)=S(n,i+1)+e=1∑pie+1≤nf(pie)(S(⌊pien⌋,i+1)+G(⌊pien⌋,limit)−j=1∑if(pj))+f(pie+1)
首先,由于 f(i) 仅仅满足是积性函数,所以我们还需要钦定 pi 的次数 e ,把 pi 这个质因子完全消去(此时我们需要 f(i) 满足是积性函数)。考虑一个合数除掉 pie 还剩什么:质数;合数;1 。
我们先不管上式中 pie+1≤n 的上界限制,考虑该怎么简便准确地求解。
首先,对于合数,新增的值就是 f(pie)S(⌊pien⌋,i+1) 。因为此处有 ⌊pien⌋ ,所以上界可以设为 pie+1≤n 。
然后,对于质数,新增的值就是 f(pie)j=i+1∑limitf(pj)[pjpie≤n] (注意这个方括号是不可或缺的!)。我们转化为 G(⌊pien⌋,limit)−j=1∑if(pj) 。此时的细节为每一次要保证 ⌊pien⌋≥pi (因为后面要减去 f(pj))。于是可以得到上界为 pie+1≤n 。
上界统一自然是最好。所以对于 1 ,如果我们加在里面,我们不仅上界要改成 pe≤n ,而且还要减去 f(p) 。所以我们干脆提出来,变成 f(pie+1) 。于是上界都统一了。
考虑完转移,我们来考虑如何设置初值。显然,S(n,limit+1) 相当于什么也没有。于是我们不用赋初值。
最后 S(n,1)+G(n,limit)+f(1) 就是所求。
一般而言,Min_25 筛的题目都是跑 1010 的,多一个 10 会相当吃力。
实现细节
1.可以发现,如果我们直接实现,S 和 G 的第一维的下标都达到了 n ,显然不行。我们考虑我们在整个算法流程中只用到了 ∀i,⌊in⌋ 的值,而这只有 n 个,所以我们提前预处理这 n 个位置,下标的范围就控制在了 n 级别。
2.求 G 和 S 中都对上界有明确要求。首先,这个上限是必须要满足的,否则可能我们在 G(⌊pin⌋,i−1) 或者 G(⌊pien⌋,limit) 中并没有加上算某个 pj ,而之后去除质数的贡献的时候又把 pj 去掉了。除了正确性的保证,我们还可以发现,当 pi2>n 时,两者都可以直接 break ,而这一步也是保证 Min_25 筛的复杂度的关键。